package 剑指offer;

public class 剑指Offer47礼物的最大价值 {

    public  int maxValue1(int[][] grid){
        if (grid.length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        if (m == 1 && n == 1) return grid[0][0];
        //否则存在两个以上得元素,创建一个状态容器
        int[][] dp = new int[m][n];
        //初始化状态容器,basecase ： 走到最后一个元素得位置，他的价值就只是他自己
        dp[m-1][n-1] = grid[m-1][n-1];
        //填表
        //从最后一个元素道第一个元素，要走m+n-1步
        for (int i = m-1,j = n-1;j > 0;j--){
            dp[i][j-1] = grid[i][j-1] + dp[i][j];
        }

        for (int i = m-1,j = n-1;i > 0;i--){
            dp[i-1][j] = dp[i][j] + grid[i][j];
        }

        for(int i = m - 2;i >= 0; i--){
            for (int j = n-2;j >= 0;j--){
                int p1 = grid[i][j] + dp[i+1][j];
                int p2 = grid[i][j] + dp[i][j-1];
                dp[i][j] = Math.max(p1,p2);
            }
        }
        return dp[0][0];
    }









    public int maxValue(int[][] grid) {
        if(grid.length == 0) return 0;//如果长度为0，直接返回价值为0，
        if(grid.length == 1 && grid[0].length == 1) return grid[0][0];//如果只有一个元素，那么就返回该元素
        int m = grid.length;//二维数组有几行
        int n = grid[0].length;//二维数组有几列
        int p1 = grid[0][0] + help(grid,0,1,m,n);
        int p2 = grid[0][0] + help(grid,1,0,m,n);
        return Math.max(p1,p2);
    }

    private int help(int[][] arr,int i,int j,int m,int n){
        if(i >= m || j >= n) return 0;

        if(i == m-1 && j == n-1){
            return arr[i][j];
        }

        int p1 = arr[i][j] + help(arr,i+1,j,m,n);
        int p2 = arr[i][j] + help(arr,i,j+1,m,n);
        return Math.max(p1,p2);
    }
}
